#include <stdio.h>
#include <cstdlib>

typedef struct LNode {
    int data;
    struct LNode *next;
} LNode, *LinkList;

// 初始化单链表（不带头结点）
bool InitList(LinkList &L) {
    L = NULL;  // 头指针置空
    return true;
}

/**
 * 头插法：在链表头部插入元素（不带头结点）
 * @param L 链表头指针
 * @param e 要插入的元素
 * @return 插入是否成功
 */
bool List_HeadInsert(LinkList &L, int e) {
    // 创建新结点
    LNode *s = (LNode *)malloc(sizeof(LNode));
    if (s == NULL) return false;  // 内存分配失败
    
    s->data = e;    // 设置新结点数据
    s->next = L;    // 新结点指向原第一个结点
    L = s;          // 头指针指向新结点
    return true;
}

/**
 * 尾插法：在链表尾部插入元素（不带头结点）
 * @param L 链表头指针
 * @param e 要插入的元素
 * @return 插入是否成功
 */
bool List_TailInsert(LinkList &L, int e) {
    // 创建新结点
    LNode *s = (LNode *)malloc(sizeof(LNode));
    if (s == NULL) return false;  // 内存分配失败
    
    s->data = e;   // 设置新结点数据
    s->next = NULL; // 新结点作为尾结点
    
    if (L == NULL) {
        // 链表为空，新结点是第一个结点
        L = s;
    } else {
        // 查找当前尾结点
        LNode *p = L;
        while (p->next != NULL) {
            p = p->next;
        }
        p->next = s;  // 原尾结点指向新结点
    }
    return true;
}

/**
 * 批量头插法创建链表（不带头结点）
 * @param L 链表头指针
 * @param arr 要插入的元素数组
 * @param n 数组长度
 */
void CreateList_Head(LinkList &L, int arr[], int n) {
    InitList(L);  // 初始化链表
    for (int i = 0; i < n; i++) {
        List_HeadInsert(L, arr[i]);
    }
}

/**
 * 批量尾插法创建链表（不带头结点）
 * @param L 链表头指针
 * @param arr 要插入的元素数组
 * @param n 数组长度
 */
void CreateList_Tail(LinkList &L, int arr[], int n) {
    InitList(L);  // 初始化链表
    
    for (int i = 0; i < n; i++) {
        List_TailInsert(L, arr[i]);
    }
}

// 销毁单链表
void DestroyList(LinkList &L) {
    LNode *p = L;       // 指向当前结点
    while (p != NULL) { // 遍历链表
        LNode *temp = p;
        p = p->next;    // 移动到下一结点
        free(temp);     // 释放当前结点
    }
    L = NULL;  // 头指针置空
}

// 打印链表内容
void PrintList(LinkList L) {
    LNode *p = L;
    printf("List: [");
    while (p != NULL) {
        printf("%d", p->data);
        if (p->next != NULL) printf("->");
        p = p->next;
    }
    printf("]\n");
}

int main() {
    LinkList L1, L2;
    
    // 头插法创建链表
    int arr1[] = {1, 2, 3, 4};
    CreateList_Head(L1, arr1, 4);
    PrintList(L1);  // 输出: List: [4->3->2->1]
    
    // 尾插法创建链表
    int arr2[] = {1, 2, 3, 4};
    CreateList_Tail(L2, arr2, 4);
    PrintList(L2);  // 输出: List: [1->2->3->4]
    
    // 头插法插入新元素
    List_HeadInsert(L1, 5);
    PrintList(L1);  // 输出: List: [5->4->3->2->1]
    
    // 尾插法插入新元素
    List_TailInsert(L2, 5);
    PrintList(L2);  // 输出: List: [1->2->3->4->5]
    
    DestroyList(L1);
    DestroyList(L2);
    return 0;
}